
package estructuraGrafo;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * Clase Grafo: Esta clase representa al Grafo
 * 
 * @author  Grupo N11
 * @author  Prinsich Bernz, Emilio J. A.
 * @author 	Solia, Guillermo D.
 * @version  1.0
 */

public class Grafo implements Serializable{

	private static final long serialVersionUID = 1L;
	/**Lista de nombre de los nodos para un acceso mas rapido de consulta*/
	private ArrayList <String> nombres;
	/**Lista de aristas del grafo*/
	private ArrayList <Arco> aristas;
	/**Lista de nodos del grafo*/
	private Hashtable <String,Nodo> nodos;
	/**Tamnio de Grafo*/
	int tamanio;

	public Grafo(){
		nombres=new ArrayList<String>();
		nodos=new Hashtable <String,Nodo>();
		aristas=new ArrayList <Arco>();
		tamanio = 0;
	}

	/**
	 * Ingresa un Nodo al Grafo
	 * @param nombre Nombre del nodo
	 * @param n tipo de nodo
	 */
	public void ingresarNodo(String nombre, int n){
		nombres.add(nombre);
		nodos.put(nombre,new Nodo(nombre, n, tamanio));
		++tamanio;
	}
	
	/**
	 * Crea los enlaces que existen entre los nodos
	 * @param nodoInicial
	 * @param nodoTerminal
	 * @param nombre
	 * @param distancia
	 * @param costo
	 * @param caudal
	 * @param b estodo del mismo
	 */
	public void adicionarEnlace(String nodoInicial,String nodoTerminal,String nombre, float distancia, float costo, int caudal, boolean b){
		Arco nuevo=new Arco(nodoInicial, nodoTerminal, nombre, distancia, costo, caudal, b);//Crea el arco del grafo
		int i=buscarIndice(nuevo.getNombre());//busca el indice del nodo

		if(i==-1)//si es -1 crea uno nuevo
			aristas.add(nuevo);
		else//agrega al existente
			aristas.add(i,nuevo);
		
		nodos.get(nodoInicial).agregarEnlace(nodoTerminal, nombre, distancia, costo, caudal, b);//crea en el nodo el enlace
		//nodos.get(nodoTerminal).agregarEnlace(nodoInicial, nombre, distancia, costo, caudal, b);
		
	}
	
	/**
	 * busca una Arista determinada y retorna true si existe
	 * @param arco  Arsita a buscar
	 * @return true si lo encontro, false de lo contrario
	 */
	public boolean busarArista(Arco arco){
		for(int i=0;i<aristas.size();i++){
			Arco otro=aristas.get(i);
			if(arco.getInicial().equals(otro.getInicial()) && arco.getTerminal().equals(otro.getTerminal())&&arco.getNombre().equals(otro.getNombre()))	{
				aristas.remove(otro);
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Busca el indice posicional de una arista determinada sino retorna -1
	 * @param string Nombre de la arista
	 * @return indice de la arista
	 */
	public int buscarIndice(String string){
		for(int i=0;i<aristas.size();i++){
 			if(string.equals(aristas.get(i).getNombre()))
				return i;
		}
		return -1;
	}
	
	/**
	 * Metodo para verificar si existen ciclos
	 * @param origen Origen del supuesto ciclo
	 * @param strDestino Destino del mismo
	 * @return True si existe ciclo
	 */
	public boolean hayCiclo(String origen, String strDestino){
		Nodo destino = getNodo(strDestino);
		
		Set<Nodo> listaDestinos = anchura(destino);
		
		for(Nodo node : listaDestinos){
			if(node.getNombre().equals(origen)){
				return true;
			}
		}
		return false;
	}

	/**
	 * Metodo para realizar una busqueda por anchura
	 * @param destino Nodo de Origen de la Busqueda
	 * @return Set de nodo
	 */
	private Set<Nodo> anchura(Nodo destino) {
		Set<Nodo> listaNodos = new LinkedHashSet<Nodo>();
		Queue<Nodo> destinos = new LinkedList<Nodo>();
		destinos.offer(destino);
		
		//realiza la busqueda en achura
		while(!destinos.isEmpty()){
			Nodo n = destinos.poll();
			//encolar los adyacentes
			Set<Nodo> adyacentes = listarAdyacentes(n);
			for(Nodo adyacente: adyacentes ){
				if(!listaNodos.contains(adyacente)){
					destinos.offer(adyacente);
				}
			}			
			listaNodos.add(n);
		}
		return listaNodos;
	}

	/**
	 * Metodo para Listar los nodos adyacente a un nodo especificado
	 * @param n Nodo a buscar sus adyacentes
	 * @return Set de nodos adyacentes
	 */
	private Set<Nodo> listarAdyacentes(Nodo n) {
		
		Set<Nodo> listaAdyacentes = new LinkedHashSet<Nodo>();
		for(Enlace link : n.getEnlaces()){
			if(link.isEstado()){
				Nodo node = getNodos().get(link.getDestino());
				listaAdyacentes.add(node);
			}
		}
		return listaAdyacentes;
	}

	public Hashtable<String, Nodo> getNodos(){
		return nodos;
	}

	/**
	 * retorna una lista de nodos
	 * @return lista de Nodos
	 */
	public ArrayList<Nodo> getListaNodos(){
		ArrayList<Nodo> listaNodos = new ArrayList<Nodo>();
		
		for(int i = 0; i < nombres.size(); i++){
			listaNodos.add(nodos.get(nombres.get(i)));
		}
		
		return listaNodos;
	}
	
	public void setNodos(Hashtable<String,Nodo> muchos){
		nodos=muchos;
	}

	public ArrayList<String> getNombres(){
		return nombres;
	}
	
	/**
	 * retorna las avenidas de las aristas
	 * @return lista de nombre de la avenidas
	 */
	public ArrayList<String> getAvenida(){
		ArrayList<String> avenidas = new ArrayList<String>();
		for(Arco i : aristas)
			avenidas.add(i.getNombre());
		return avenidas;
	}
	
	public Nodo getNodo(String nombre){
		return nodos.get(nombre);
	}

	public ArrayList<Arco> getAristas(){
		return aristas;
	}

	public void setAristas(ArrayList<Arco> aristas){
		this.aristas = aristas;
	}

	public void setNombres(ArrayList<String> nombres){
		this.nombres = nombres;
	}
	
	public int size(){ return tamanio; }

	public void aumentarNivel(String origen, String destino) {
		Nodo node = getNodo(origen);
		getNodo(destino).setNivel(node.getNivel() +1);
	}

	public void clone(Grafo grafo){
		nombres=new ArrayList<String>();
		nodos=new Hashtable <String,Nodo>();
		aristas=new ArrayList <Arco>();
		tamanio = 0;
		
		for(Nodo node: grafo.getListaNodos()){
			ingresarNodo(node.getNombre(), node.getTipo());
		}
		for(Arco arc: grafo.getAristas()){
			adicionarEnlace(arc.getInicial(), arc.getTerminal(), arc.getNombre(), arc.getDistancia(), arc.getCosto(), arc.getCaudal(), arc.isEstado());
			aumentarNivel(arc.getInicial(), arc.getTerminal());
		}
	}
}